\section{Probability calculations}
 \label{sec:prob_calc}
 
The following small Ruby-program calculates the probability that an
adversarial controlling a number of IP addresses control the majority
of the OPs.

The significant variables are the number of peers in the network, the number of IDs that an adversarial can get (which is equal to the number of of IP addresses that an adversarial control), the number of OPs for a game, and the number of OPs that an adversarial must control to have the majority.

We have chosen to think in terms of a deck of cards. We then calculate the probability of drawing at least a certain number of aces from the deck when you draw a certain number of cards.

\begin{itemize}
\item cards: the number of cards in the deck. Corresponds to the number of peers in the network.
\item draws: the number of cards to be drawn. Corresponds to the number of IP addresses that the adversarial controls.
\item aces: the number of aces in the deck. Corresponds to the number of OPs for a game.
\item drawAces: the number of aces that must at least be drawn. Corresponds to the number of OPs that an adversarial must control to have the majority.
\end{itemize}

The probability of an adversarial controlling the majority of the OPs should correspond to the probability of drawing the number of aces. In our calculations, when card is drawn, it is taken out of the deck. We have done this to ease the calculations.

To correspond exactly to our network, when a card is drawn that is not an ace, the card should be put back into the deck (since the IDs are hashes of the IPs, and the hash function uniformly maps the IPs to the IDs).

Therefore we calculate a probability that is a little bit too big, because it is easier to draw the aces when you can throw away cards that are not aces. We believe however that we are close to the real result because we only care about situations where the number of cards in the deck is much bigger than the number of cards to be drawn.

In any case, we get an upperbound for the probability that an adversarial can gain control of the majority of the OPs.
